// https://leetcode.cn/problems/contains-duplicate/description/

// 算法思路总结：
// 1. 使用哈希表记录数字出现次数
// 2. 遍历数组，检查数字是否已存在
// 3. 存在则返回true，否则记录数字
// 4. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <unordered_map>

class Solution 
{
public:
    bool containsDuplicate(vector<int>& nums) 
    {
        int n = nums.size();
        unordered_map<int, int> up;

        for (int i = 0 ; i < n ; i++)
        {
            if (up.count(nums[i]) > 0)
            {
                return true;
            }
            else up[nums[i]] = 1;
        }

        return false;
    }
};

int main()
{
    vector<int> v1 = {1,2,3,1}, v2 = {1,2,3,4};
    Solution sol;

    cout << sol.containsDuplicate(v1) << endl;
    cout << sol.containsDuplicate(v2) << endl;

    return 0;
}